package com.zang.greedy;

import java.util.Arrays;

/**
 * @author ZVerify
 * @since 2022/11/21 22:34
 * @see <a href="https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/">...</a>
 **/
public class K次取反后最大化的数组和 {

    public int largestSumAfterKNegations(int[] nums, int k) {
        // 先排序为的就是先操作负数
        Arrays.sort(nums);
        int i = 0;
        while (k>0 && i<nums.length && nums[i]<0 ){
            nums[i] = -nums[i];
            k--;
            i++;
        }
        Arrays.sort(nums);

        // 如果翻转次数用完直接返回
        if (k==0) return Arrays.stream(nums).sum();
        // 走到这里的话就是次数没用完或者遇到正数了，遇到正数就是当前都为正数了所以需要重新排序
        Arrays.sort(nums);
        // 5. 判断剩余翻转次数是否为奇数, 如果是奇数则将第一个元素翻转(最小正数变负数, 对最终结果影响最"小")
        if (k % 2 != 0) {
            nums[0] = -nums[0];
        }

        return Arrays.stream(nums).sum();

    }
}
